package LeetCode;

public class Solution {
    /**
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int flag = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] < nums[i]) {
                nums[flag] = nums[i];
                flag++;
                System.out.println(nums[flag-1]);
            }
        }
        return flag;
    }

    /**
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int fit = 0;

        for (int i = 0; i <= prices.length-1; i++) {
            if (prices[i] < prices[i+1]) {
                fit += prices[i+1] - prices[i];
            }
        }
        return fit;
    }

    /**
     *
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k) {
        int s1 = 0;
        int s2;
        int flag = 0;

        int parts = gcd(nums.length, k);
        for (int i = 0; i < parts; i++) {
            s2 = nums[flag];
            for (int j = 0; j < nums.length/parts; j++) {
                if ((j%2) != 0) {
                    s2 = nums[(flag+k)%nums.length];
                    nums[(flag+k)%nums.length] = s1;
                } else {
                    s1 = nums[(flag+k)%nums.length];
                    nums[(flag+k)%nums.length] = s2;
                }
                flag = (flag+k)%nums.length;
            }
            flag = i + 1;
        }
    }

    public static int gcd(int a,int b){
        if(b==0){
            return a;
        }
        int r=a%b;
        return gcd(b,r);
    }

    public static void rotate2(int[] nums, int k) {
        int l = nums.length - 1;
        k = k % (l + 1);
        reverse(nums, 0, l);
        reverse(nums, k, l);
        reverse(nums, 0, k-1);
    }
    public static void reverse(int[] nums, int start, int end) {
        int buffer;
        while(start < end) {
            buffer = nums[start];
            nums[start] = nums[end];
            nums[end] = buffer;
            start++;
            end--;
        }
    }

    /**
     * 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
     * @param nums 被检验的数组
     * @return 是否有重复的布尔值
     */
    public static boolean containsDuplicate(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i+1]) return true;
        }
        return false;
    }

    public static boolean containsDuplicate1(int[] nums) {
        int n=nums.length;
        int min=nums[0],max=nums[0];
        if(n<2)
            return false;
        for(int i=1;i<n;i++){
            if(min>nums[i]){
                min=nums[i];
                continue;
            }
            if(max<nums[i]){
                max=nums[i];
                continue;
            }
            if(min==nums[i]||max==nums[i]) return true;
            for(int j=0;j<i;j++){
                if(nums[j]==nums[i])
                    return true;
            }
        }
        return false;
    }

    public static void quickSort(int[] arr, int low, int high) {
        int i, j, temp, t;

        if (low > high) return;

        i = low;
        j = high;
        temp = arr[i];

        while (i < j) {
            while (arr[j] >= temp && i < j) {
                j--;
            }
            while (arr[i] <= temp && i < j) {
                i++;
            }

            if (i < j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }

        arr[low] = arr[i];
        arr[i] = temp;

        quickSort(arr, low, i-1);
        quickSort(arr, i+1, high);
    }
}
